package DataStructureAndAlgorithm.Acwing.DP.背包问题DP.计数DP;

import java.util.Scanner;

class dp_1021{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] money = new int[n + 1];
        //dp[i][j]：表示所有从前i种钱中拿，并且钱数恰好为j的所有选择的方案
        long[][] dp = new long[n + 1][m + 1];
        for (int i = 1; i <= n; i++){
            money[i] = in.nextInt();
        }
        //所有从前i个数中选，和为0的方案数都默认为1，即都不选也为一种方案
        for (int i = 0; i <= n; i++)dp[i][0] = 1;
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                for (int k = 0; k * money[i] <= j; k++){
                    //当前的方案数 = 选当前数的方案数 + 不选当前数的方案数
                    //因为k从0开始，所以当k=0时，即为不选的情况，
                    //所以，此时不选的方案表示为：dp[i][j] = dp[i - 1][j] + dp[i][j];
                    dp[i][j] = dp[i - 1][j - k * money[i]] + dp[i][j];
                }
            }
        }
        System.out.print(dp[n][m]);
    }
}

